Le Support Vector Machines (SVM) sono la tecnica più popolare della famiglia dei metodi kernel introdotta nel capitolo precedente, e nascono per risolverne il difetto principale: il costo di soluzioni che dipendono da tutti i campioni del training set. L’idea è duplice. Da un lato si cambia il criterio con cui si sceglie l’iperpiano separatore: non una separazione qualsiasi, come nel perceptron, ma quella che massimizza il margine, cioè la distanza dai punti più vicini. Dall’altro, la matematica di questo criterio (un problema di ottimizzazione quadratica, risolto passando per la dualità lagrangiana) produce gratuitamente due proprietà preziose: la soluzione si scrive solo in termini di kernel, quindi eredita tutta la potenza dei metodi kernel, ed è sparsa, cioè dipende solo da un piccolo sottoinsieme di campioni detti support vector. Il capitolo sviluppa l’intera catena: definizione del margine, formulazione primale, passaggio al duale con moltiplicatori di Lagrange e condizioni KKT, ruolo dei support vector, confini non lineari tramite kernel, estensione soft margin per dati non separabili, addestramento pratico, estensioni multi-classe e a regressione. Chiude una sezione di esercizi svolti in stile esame, con la procedura meccanica per trovare support vector, pesi e margine di un piccolo dataset: la tipologia numerica più frequente negli esami del corso.

Riferimenti sul testo: Bishop, Pattern Recognition and Machine Learning, capitolo 7 (7.1, 7.1.1, 7.1.3, 7.1.4) e Appendice E per i moltiplicatori di Lagrange.

1. Dai metodi kernel alle macchine kernel sparse#

1.1 Il problema: soluzioni che dipendono da tutti i campioni#

Il capitolo sui metodi kernel ha mostrato come sia possibile lavorare implicitamente in feature space enormi, anche a dimensionalità infinita, senza mai calcolare esplicitamente le feature: basta saper calcolare la funzione kernel $k(\mathbf{x}, \mathbf{x}') = \boldsymbol{\phi}(\mathbf{x})^T \boldsymbol{\phi}(\mathbf{x}')$. Il prezzo di questa potenza è però rimasto in sospeso. Per addestrare un modello kernel serve la matrice di Gram, la matrice $N \times N$ dei kernel tra tutte le coppie di campioni; e la soluzione trovata, per esempio nella kernel ridge regression, è una combinazione che coinvolge tutti gli $N$ campioni del training set: il vettore dei coefficienti duali ha una componente per campione, non per feature. Ogni predizione su un punto nuovo richiede quindi di valutare il kernel tra quel punto e ogni campione del training set. Con $N$ grande, sia l’addestramento sia l’inferenza diventano computazionalmente proibitivi.

1.2 L’obiettivo: sparsità#

Idea chiave: mantenere il vantaggio dei kernel (modelli molto espressivi senza calcolare le feature) eliminando il costo: cercare soluzioni in cui la maggior parte dei coefficienti duali è esattamente zero, così che solo pochi campioni contribuiscano alla predizione.

I metodi che realizzano questo programma si chiamano sparse kernel machines: trovano soluzioni che dipendono solo da un sottoinsieme dei campioni di training. I due rappresentanti più noti sono le Support Vector Machines e le Relevance Vector Machines (RVM); il corso si concentra sulle prime, di gran lunga le più diffuse. Nelle SVM i pochi campioni con coefficiente non nullo hanno un nome e un’interpretazione geometrica precisa: sono i support vector, i punti che “sostengono” la superficie di separazione.

In parole semplici: i metodi kernel puri sono come un comitato in cui ogni singolo dato del training set ha diritto di parola a ogni decisione: potentissimo ma lentissimo. Le SVM riducono il comitato ai soli membri davvero informativi, quelli al confine tra le classi, e ignorano tutti gli altri.

2. Non tutte le separazioni sono uguali: il margine#

2.1 Richiami: la geometria del discriminante lineare#

Il punto di partenza delle SVM è il modello del perceptron, già studiato nella parte sulla classificazione lineare. Il classificatore è

$$\hat{t}(\mathbf{x}) = \text{sign}\big( y(\mathbf{x}) \big), \qquad y(\mathbf{x}) = \mathbf{w}^T \boldsymbol{\phi}(\mathbf{x}) + b$$

con target codificati come $t_n \in \{-1, +1\}$. La superficie di decisione è il luogo $y(\mathbf{x}) = 0$, un iperpiano nel feature space, e valgono le proprietà geometriche già derivate:

• l’iperpiano è ortogonale a $\mathbf{w}$;
• la distanza dell’iperpiano dall’origine è $-\dfrac{b}{\lVert \mathbf{w} \rVert_2}$;
• la distanza (con segno) di un punto $\mathbf{x}$ dall’iperpiano è $\dfrac{y(\mathbf{x})}{\lVert \mathbf{w} \rVert_2}$.

L’ultima proprietà è quella cruciale: il valore di $y(\mathbf{x})$, riscalato per la norma dei pesi, misura quanto un punto è lontano dal confine di decisione, e il suo segno dice da che parte sta. In particolare, un punto è classificato correttamente se e solo se $t_n \, y(\mathbf{x}_n) > 0$: moltiplicare per il target trasforma la distanza con segno in una quantità positiva per i punti dal lato giusto, esattamente come farebbe un valore assoluto ma restando una funzione liscia dei parametri.

2.2 Il limite del perceptron#

Il perceptron, applicabile quando il problema è linearmente separabile, minimizza una perdita proporzionale all’entità degli errori sui soli punti misclassificati; quando trova una separazione perfetta la perdita è zero e l’algoritmo si ferma. Il difetto è che il perceptron non esprime alcuna preferenza tra le infinite separazioni perfette possibili: qualunque iperpiano che separa i dati azzera la perdita, e quale venga effettivamente trovato dipende solo dall’inizializzazione dei pesi e dall’ordine di presentazione dei campioni.

Eppure le soluzioni non sono affatto equivalenti. Si immaginino tre iperpiani che separano tutti lo stesso dataset: due passano rasenti ad alcuni punti, il terzo scorre a distanza ragionevole da entrambe le classi. Intuitivamente il terzo è preferibile: un punto di test appena diverso dai punti di training (per rumore o per naturale variabilità) finirebbe facilmente dal lato sbagliato di un confine che passa a un soffio dai dati, mentre un confine “largo” tollera perturbazioni. La qualità di una separazione non è solo separare, è separare con riserva di sicurezza.

2.3 Il margine e il classificatore a massimo margine#

Il classificatore a massimo margine cerca l’iperpiano che rende questa distanza la più grande possibile:

$$\mathbf{w}^*, b^* = \arg\max_{\mathbf{w}, b} \left\{ \frac{1}{\lVert \mathbf{w} \rVert_2} \min_n \, t_n \big( \mathbf{w}^T \boldsymbol{\phi}(\mathbf{x}_n) + b \big) \right\}$$

Un’osservazione geometrica utile: nella soluzione ottima la distanza dal punto positivo più vicino e quella dal punto negativo più vicino devono essere uguali. Se fossero diverse, si potrebbe traslare l’iperpiano verso la classe più lontana guadagnando margine; quindi qualunque iperpiano con distanze diverse dai due lati non può essere ottimo.

In parole semplici: tra tutte le rette (o iperpiani) che separano i dati, la SVM sceglie quella che passa “più al centro” possibile del corridoio vuoto tra le due classi, alla stessa distanza dai punti più vicini di entrambe. È lo stesso criterio con cui si guida in una strettoia: al centro, il più lontano possibile da entrambi i muri.

Il problema così scritto, un massimo di un minimo con una frazione, è però molto scomodo da ottimizzare direttamente. Serve una riformulazione.

3. La formulazione primale#

3.1 L’iperpiano canonico#

La prima semplificazione nasce da un’osservazione: il problema, così com’è, è mal posto perché ha infinite soluzioni equivalenti. Se $(\mathbf{w}^*, b^*)$ definisce un certo iperpiano, allora $(\kappa \mathbf{w}^*, \kappa b^*)$ per qualunque costante $\kappa > 0$ definisce esattamente lo stesso iperpiano: l’equazione $y(\mathbf{x}) = 0$ non cambia moltiplicando tutto per una costante positiva, e nemmeno il margine cambia, perché il fattore $\kappa$ compare sia al numeratore (dentro $y$) sia al denominatore (dentro $\lVert \mathbf{w} \rVert_2$) e si semplifica. La scala di $\mathbf{w}$ e $b$ è quindi irrilevante per la geometria, ma lascia l’ottimizzazione con infinite soluzioni indistinguibili.

Per fissare la scala si sceglie, tra le infinite versioni equivalenti, quella detta iperpiano canonico: si impone che per il punto (o i punti) più vicini all’iperpiano valga

$$t_n \big( \mathbf{w}^T \boldsymbol{\phi}(\mathbf{x}_n) + b \big) = 1$$

cioè che la funzione $y$ valga esattamente $+1$ sui punti positivi a ridosso del margine e $-1$ su quelli negativi. Con questa normalizzazione:

• il margine diventa semplicemente $\dfrac{1}{\lVert \mathbf{w} \rVert_2}$ (e l’ampiezza totale del corridoio tra le due classi è $\dfrac{2}{\lVert \mathbf{w} \rVert_2}$);
• tutti gli altri punti, essendo più lontani, soddisfano $t_n \, y(\mathbf{x}_n) > 1$;
• ogni iperpiano geometrico corrisponde ora a una sola coppia $(\mathbf{w}, b)$.

In parole semplici: siccome moltiplicare pesi e bias per una costante non cambia la retta di separazione, si sfrutta questa libertà per fissare una convenzione comoda: sui punti più vicini la funzione deve valere esattamente $\pm 1$. Da quel momento il margine si legge direttamente dalla norma dei pesi: pesi piccoli significano margine grande.

3.2 Il problema quadratico primale#

Con la normalizzazione canonica, massimizzare il margine $1/\lVert \mathbf{w} \rVert_2$ equivale a minimizzare $\lVert \mathbf{w} \rVert_2$, e per convenienza si minimizza la norma al quadrato (i problemi quadratici hanno ottimi algoritmi dedicati e derivate semplici). Il vincolo di canonicità, insieme al fatto che tutti i punti devono stare sul lato giusto e fuori dal margine, dà i vincoli del problema.

Questa formulazione definisce completamente il problema, ma non è ancora la forma finale della SVM. Il motivo è lo stesso che ha motivato i kernel: $\boldsymbol{\phi}(\mathbf{x}_n)$ può vivere in uno spazio a dimensionalità enorme o infinita, e non si vuole mai doverlo calcolare esplicitamente. Serve una riscrittura del problema in cui i vettori di feature compaiano solo attraverso prodotti scalari, sostituibili con kernel: è il passaggio al problema duale.

4. Dal primale al duale: moltiplicatori di Lagrange e KKT#

4.1 La lagrangiana#

Lo strumento standard per l’ottimizzazione vincolata sono i moltiplicatori di Lagrange (la trattazione completa, con tutti i casi, è nell’Appendice E del Bishop; qui servono il meccanismo e l’intuizione). Si introduce una nuova variabile $\alpha_n \geq 0$ per ogni vincolo, si riscrive ciascun vincolo nella forma “$\geq 0$”, cioè $t_n(\mathbf{w}^T\boldsymbol{\phi}(\mathbf{x}_n) + b) - 1 \geq 0$, e si costruisce la funzione lagrangiana sottraendo all’obiettivo i vincoli pesati dai moltiplicatori:

$$\mathcal{L}(\mathbf{w}, b, \boldsymbol{\alpha}) = \frac{1}{2} \lVert \mathbf{w} \rVert_2^2 \; - \; \sum_{n=1}^{N} \alpha_n \Big[ t_n \big( \mathbf{w}^T \boldsymbol{\phi}(\mathbf{x}_n) + b \big) - 1 \Big], \qquad \alpha_n \geq 0$$

La lagrangiana va minimizzata rispetto alle variabili originali $\mathbf{w}$ e $b$ e massimizzata rispetto ai moltiplicatori $\boldsymbol{\alpha}$. L’intuizione del meccanismo: se un vincolo viene violato, il termine tra parentesi quadre diventa negativo; massimizzando su $\alpha_n \geq 0$, il moltiplicatore corrispondente può crescere e far esplodere la penalità, quindi la soluzione ottima del gioco min-max non può contenere violazioni. I moltiplicatori agiscono da “prezzi” delle violazioni.

4.2 Le condizioni di stazionarietà#

Si annullano i gradienti della lagrangiana rispetto alle variabili primali:

$$\frac{\partial \mathcal{L}}{\partial \mathbf{w}} = 0 \;\; \Rightarrow \;\; \mathbf{w} = \sum_{n=1}^{N} \alpha_n t_n \boldsymbol{\phi}(\mathbf{x}_n) \qquad\qquad \frac{\partial \mathcal{L}}{\partial b} = 0 \;\; \Rightarrow \;\; \sum_{n=1}^{N} \alpha_n t_n = 0$$

La prima equazione è un cambio di variabile fondamentale: il vettore dei pesi ottimo è una combinazione lineare dei vettori di feature dei campioni, con coefficienti $\alpha_n t_n$. Questo permette di eliminare $\mathbf{w}$ dal problema, sostituendolo ovunque con questa espressione. La seconda equazione è un vincolo aggiuntivo che lega i moltiplicatori ai target e che entrerà nel problema duale.

4.3 Il problema duale#

Sostituendo $\mathbf{w} = \sum_n \alpha_n t_n \boldsymbol{\phi}(\mathbf{x}_n)$ nella lagrangiana e sfruttando $\sum_n \alpha_n t_n = 0$, le variabili $\mathbf{w}$ e $b$ scompaiono del tutto e resta un problema nella sola $\boldsymbol{\alpha}$.

Il calcolo esplicito della sostituzione

I passaggi sono meccanici ma vale la pena vederli una volta, perché “derivare il duale dal primale” è una domanda d’esame ricorrente. Sostituendo l’espressione di $\mathbf{w}$:

$$\frac{1}{2}\lVert \mathbf{w} \rVert_2^2 = \frac{1}{2} \left( \sum_n \alpha_n t_n \boldsymbol{\phi}(\mathbf{x}_n) \right)^{\!T} \! \left( \sum_m \alpha_m t_m \boldsymbol{\phi}(\mathbf{x}_m) \right) = \frac{1}{2} \sum_{n}\sum_{m} \alpha_n \alpha_m t_n t_m \, k(\mathbf{x}_n, \mathbf{x}_m)$$

$$\sum_n \alpha_n t_n \mathbf{w}^T \boldsymbol{\phi}(\mathbf{x}_n) = \sum_{n}\sum_{m} \alpha_n \alpha_m t_n t_m \, k(\mathbf{x}_n, \mathbf{x}_m), \qquad b \sum_n \alpha_n t_n = 0$$

La lagrangiana diventa quindi

$$\mathcal{L} = \frac{1}{2}\sum_{n}\sum_{m} \alpha_n \alpha_m t_n t_m k(\mathbf{x}_n, \mathbf{x}_m) - \sum_{n}\sum_{m} \alpha_n \alpha_m t_n t_m k(\mathbf{x}_n, \mathbf{x}_m) + \sum_n \alpha_n = \sum_n \alpha_n - \frac{1}{2}\sum_{n}\sum_{m} \alpha_n \alpha_m t_n t_m k(\mathbf{x}_n, \mathbf{x}_m)$$

che è l’obiettivo duale da massimizzare.

Il punto qualificante è l’ultima riga: nell’obiettivo duale i vettori di feature sopravvivono solo dentro prodotti scalari, che si possono valutare con la funzione kernel senza mai costruire le feature. Per risolvere l’ottimizzazione basta conoscere il kernel: esattamente l’obiettivo dichiarato all’inizio. In più, il numero di variabili è $N$ invece della dimensionalità del feature space (che nel primale determina la taglia di $\mathbf{w}$ e può essere infinita).

In parole semplici: il passaggio al duale è un cambio di prospettiva: invece di cercare direttamente i pesi dell’iperpiano, si cerca “quanto conta” ciascun punto del dataset (il suo $\alpha_n$). I pesi si ricostruiscono poi come combinazione dei punti pesati per la loro importanza. Il guadagno è che in questa forma servono solo le similarità tra coppie di punti, cioè i kernel, mai le coordinate nel feature space.

4.4 Le condizioni KKT#

Per problemi convessi con vincoli di disuguaglianza, la soluzione ottima è caratterizzata dalle condizioni di Karush-Kuhn-Tucker (KKT).

La condizione di complementarietà è quella da cui discende tutta la struttura della soluzione, come si vede nella prossima sezione.

5. I support vector e la soluzione#

5.1 Sparsità: perché quasi tutti i moltiplicatori si annullano#

Risolto il duale, la funzione discriminante si ottiene sostituendo $\mathbf{w} = \sum_n \alpha_n t_n \boldsymbol{\phi}(\mathbf{x}_n)$ in $y(\mathbf{x})$:

$$y(\mathbf{x}) = \sum_{n=1}^{N} \alpha_n t_n \, k(\mathbf{x}, \mathbf{x}_n) + b$$

A prima vista sembra la solita soluzione kernel non sparsa: una somma su tutti gli $N$ campioni. La sparsità arriva dalle condizioni KKT. Per la condizione di complementarietà, per ogni punto vale $\alpha_n \big( t_n y(\mathbf{x}_n) - 1 \big) = 0$; quindi:

• se il punto non è sul margine, cioè $t_n y(\mathbf{x}_n) > 1$, la parentesi è strettamente positiva e l’unica possibilità è $\alpha_n = 0$. Intuitivamente: nella lagrangiana un $\alpha_n > 0$ moltiplicherebbe una quantità positiva sottratta all’obiettivo da massimizzare, quindi non può essere ottimale;
• se il punto è esattamente sul margine, cioè $t_n y(\mathbf{x}_n) = 1$, la parentesi è nulla e $\alpha_n$ è libero di essere positivo senza costi: sono gli unici punti che possono avere moltiplicatore non nullo.

La somma nella funzione discriminante si riduce quindi ai soli support vector:

$$y(\mathbf{x}) = \sum_{n \in \mathcal{S}} \alpha_n t_n \, k(\mathbf{x}, \mathbf{x}_n) + b$$

In un problema reale con migliaia di punti, i support vector possono essere una manciata: tutti i punti “interni” alle rispettive classi, lontani dal confine, hanno $\alpha_n = 0$ e si possono letteralmente buttare via dopo l’addestramento senza cambiare nulla. Per classificare un punto nuovo bastano i kernel tra quel punto e i pochi support vector.

In parole semplici: la posizione dell’iperpiano ottimo dipende solo dai punti che gli stanno addosso, quelli sul margine: sono loro che lo “sostengono”, come i pali sostengono una tenda. Spostare o eliminare un punto lontano dal confine non cambia niente; per questo, dopo l’addestramento, si conservano solo i support vector e la predizione diventa velocissima.

5.2 Il calcolo del bias#

Il duale determina gli $\alpha_n$ ma non direttamente $b$, che è sparito annullando il gradiente. Lo si recupera dalla proprietà canonica: ogni support vector soddisfa $t_n \, y(\mathbf{x}_n) = 1$, cioè

$$t_n \left( \sum_{m \in \mathcal{S}} \alpha_m t_m \, k(\mathbf{x}_n, \mathbf{x}_m) + b \right) = 1$$

In linea di principio basta risolvere questa equazione per $b$ usando un solo support vector qualsiasi. In pratica, per una soluzione numericamente più stabile, la si risolve per tutti i support vector e si media il risultato (moltiplicando per $t_n$ e usando $t_n^2 = 1$):

$$b = \frac{1}{|\mathcal{S}|} \sum_{n \in \mathcal{S}} \left( t_n - \sum_{m \in \mathcal{S}} \alpha_m t_m \, k(\mathbf{x}_n, \mathbf{x}_m) \right)$$

In parole semplici: ogni support vector “sa” dove deve stare il margine, quindi ognuno fornisce una stima di $b$; per non fidarsi di un punto solo, si chiede a tutti e si fa la media.

5.3 Che cosa serve davvero a runtime#

Vale la pena distinguere le due fasi. In addestramento serve l’intera matrice di Gram: il kernel tra ogni coppia di punti del training set, perché l’obiettivo duale li coinvolge tutti. In inferenza, invece, tutta l’informazione necessaria è già condensata negli $\alpha_n$ dei support vector e in $b$: per classificare un punto nuovo si calcolano solo i kernel tra il punto nuovo e i support vector (questi non si possono precalcolare, perché dipendono dal punto da classificare, ma sono pochi).

5.4 Un bound sull’errore leave-one-out#

La sparsità ha anche una conseguenza teorica elegante. Si consideri la procedura di leave-one-out: si toglie un punto, si riaddestra, si verifica se il punto tolto viene classificato correttamente. Se il punto tolto non è un support vector, la soluzione riaddestrata è identica a quella originale (il punto non contribuiva), e siccome quel punto era correttamente classificato e fuori dal margine, resta correttamente classificato: non può generare errore. Gli unici punti che possono produrre un errore leave-one-out sono quindi i support vector, da cui il bound

$$L_{LOO} \leq \frac{|\mathcal{S}|}{N}$$

cioè l’errore leave-one-out è limitato dalla frazione di support vector. Poche decine di support vector su migliaia di punti sono quindi anche un indizio di buona generalizzazione, non solo un vantaggio computazionale.

In parole semplici: se togliendo un punto la soluzione non cambia, quel punto non può essere sbagliato nel test leave-one-out. Solo i support vector possono “far danni”, quindi meno support vector ci sono, migliore è la stima dell’errore di generalizzazione.

6. SVM con kernel: confini non lineari#

Tutto il macchinario descritto vive nel feature space: lì l’iperpiano è lineare e il margine è una striscia diritta. Ma poiché sia l’addestramento (duale) sia la predizione (funzione discriminante) usano solo la funzione kernel, si può scegliere qualunque kernel valido, per esempio quello gaussiano, e ottenere confini di decisione arbitrariamente non lineari nello spazio originale: la retta nel feature space, riportata indietro, può diventare una curva qualsiasi, anche chiusa, che racchiude isole di una classe dentro l’altra. Anche le linee di margine, diritte nel feature space, appaiono come curve che affiancano il confine.

L’immagine da tenere a mente per un problema 2D con kernel gaussiano: un confine curvo e sinuoso tra le due classi, due curve di margine ai suoi lati, e una manciata di punti cerchiati (i support vector) appoggiati sulle curve di margine (e, nella variante soft margin della prossima sezione, anche sparsi nella zona di violazione). Tutti gli altri punti, per quanto numerosi, sono irrilevanti per la soluzione.

In parole semplici: la SVM disegna sempre una linea dritta, ma in uno spazio trasformato che non vediamo. Con il kernel giusto quella linea dritta, vista nel nostro spazio, può essere una curva complicata quanto serve. La combinazione “massimo margine + kernel + sparsità” è quello che ha reso le SVM per anni lo stato dell’arte della classificazione.

7. Soft margin: quando i dati non sono separabili#

7.1 Perché il margine rigido non basta#

Tutta la costruzione precedente assume che i dati siano linearmente separabili nel feature space. Con kernel abbastanza ricchi (per esempio il kernel gaussiano, che corrisponde a un feature space a dimensionalità infinita) uno spazio in cui i dati sono separabili si trova quasi sempre. Il problema è un altro: se il dataset contiene punti rumorosi o outlier, imporre la separazione perfetta costringe il modello a contorcersi per accontentare ogni singolo punto, producendo confini di decisione complessi e irregolari che inseguono il rumore. È l’overfitting nella sua versione SVM: i vincoli rigidi non lasciano al modello la libertà di sacrificare un punto anomalo in cambio di un confine più semplice.

7.2 Le variabili di slack e il primale soft margin#

Idea chiave: trasformare i vincoli rigidi in vincoli morbidi introducendo, per ogni punto, una variabile di slack $\xi_n \geq 0$ che misura di quanto quel punto viola il proprio margine; le violazioni sono ammesse ma pagate nell’obiettivo, con un prezzo unitario $C$ scelto dal progettista.

Il valore della slack ha una lettura geometrica diretta:

• $\xi_n = 0$: punto sul margine o oltre, dal lato corretto (nessuna violazione);
• $0 < \xi_n \leq 1$: punto dentro il margine ma ancora dal lato corretto del confine (violazione morbida, classificazione ancora corretta);
• $\xi_n > 1$: punto oltre il confine di decisione, cioè misclassificato.

Senza il termine $C \sum_n \xi_n$ nell’obiettivo, il modello potrebbe violare i vincoli a piacere azzerando di fatto il problema; il termine di penalità dice “puoi sbagliare, ma ogni violazione costa”.

In parole semplici: la versione soft della SVM smette di pretendere la perfezione. Ogni punto scomodo può entrare nel margine o addirittura finire dal lato sbagliato, pagando una multa proporzionale allo sconfinamento. Il modello sceglie l’equilibrio più economico tra un margine largo e il totale delle multe.

7.3 Il ruolo di C e il compromesso bias-varianza#

Il parametro $C$ è l’analogo SVM del coefficiente di regolarizzazione, ma con verso opposto rispetto al $\lambda$ della ridge regression:

• $C$ grande: le violazioni costano molto; al limite $C \to \infty$ si torna al margine rigido, che non ammette alcuna violazione. Il confine di decisione deve accomodare ogni punto rumoroso, quindi diventa più complesso e irregolare: varianza alta, bias basso, poca regolarizzazione.
• $C$ piccolo: le violazioni costano poco; il modello preferisce margini larghi e confini lisci anche a costo di sbagliare qualche punto: varianza bassa, bias alto, molta regolarizzazione. Al limite $C \to 0$ gli errori non contano più nulla.

Mentre nella ridge $\lambda$ grande significa più regolarizzazione, qui è $C$ piccolo a regolarizzare di più: informalmente $C$ si comporta come $1/\lambda$. Come ogni iperparametro, $C$ va scelto con una procedura di tuning (per esempio validazione incrociata): non esiste un valore giusto a priori.

In parole semplici: $C$ è la severità del giudice sulle multe per sconfinamento. Giudice severissimo ($C$ grande): il modello non tollera errori e si contorce per accontentare ogni punto, rischiando l’overfitting. Giudice tollerante ($C$ piccolo): il modello traccia un confine semplice e liscio, accettando qualche sbaglio. Attenzione all’esame: funziona al contrario del $\lambda$ della regolarizzazione.

7.4 Il duale soft margin: vincoli a scatola#

La derivazione del duale ricalca quella del margine rigido, con un moltiplicatore in più per i vincoli $\xi_n \geq 0$. La lagrangiana è

$$\mathcal{L}(\mathbf{w}, b, \boldsymbol{\xi}, \boldsymbol{\alpha}, \boldsymbol{\mu}) = \frac{1}{2}\lVert \mathbf{w} \rVert_2^2 + C \sum_{n=1}^{N} \xi_n - \sum_{n=1}^{N} \alpha_n \Big[ t_n y(\mathbf{x}_n) - 1 + \xi_n \Big] - \sum_{n=1}^{N} \mu_n \xi_n$$

con $\alpha_n \geq 0$ e $\mu_n \geq 0$. Le condizioni di stazionarietà rispetto a $\mathbf{w}$ e $b$ sono identiche a prima ($\mathbf{w} = \sum_n \alpha_n t_n \boldsymbol{\phi}(\mathbf{x}_n)$ e $\sum_n \alpha_n t_n = 0$); la novità è la derivata rispetto alle slack:

$$\frac{\partial \mathcal{L}}{\partial \xi_n} = C - \alpha_n - \mu_n = 0 \;\; \Rightarrow \;\; \alpha_n = C - \mu_n \leq C$$

Poiché $\mu_n \geq 0$, ogni moltiplicatore risulta limitato superiormente da $C$. Sostituendo tutto nella lagrangiana, le slack e i $\mu_n$ scompaiono e l’obiettivo duale risulta identico a quello del margine rigido; cambia solo l’insieme ammissibile.

Il valore di $\alpha_n$ ora classifica i punti in tre categorie, informazione richiesta spesso all’esame:

• $\alpha_n = 0$: il punto non è un support vector, sta fuori dal margine dal lato corretto e non contribuisce alla soluzione;
• $0 < \alpha_n < C$: support vector con $\xi_n = 0$, cioè esattamente sul margine;
• $\alpha_n = C$: support vector che viola il margine: è dentro il margine e correttamente classificato se $\xi_n \leq 1$, misclassificato se $\xi_n > 1$.

Il cap a $C$ ha anche una lettura da regolarizzazione: limita il contributo massimo che un singolo campione può dare alla soluzione. Con $C$ piccolo nessun punto, per quanto anomalo, può tirare il confine verso di sé oltre una certa forza.

In parole semplici: nel soft margin ogni punto ha un’influenza compresa tra 0 e $C$. Influenza zero: punto tranquillo lontano dal confine. Influenza intermedia: punto appoggiato esattamente sul margine. Influenza satura a $C$: punto problematico che sconfina o è proprio dal lato sbagliato; il tetto $C$ gli impedisce comunque di dominare la soluzione.

7.5 La ν-SVM#

Un difetto pratico di $C$ è che il suo valore numerico non ha alcuna interpretazione: non si sa a priori come $C = 10$ o $C = 0.1$ si tradurranno in comportamento del modello. Esiste una formulazione alternativa, la $\nu$-SVM, che sostituisce $C$ con un parametro $\nu \in (0, 1)$ dal significato trasparente:

$$\text{frazione di margin errors} \; \leq \; \nu \; \leq \; \text{frazione di support vector}$$

cioè $\nu$ è contemporaneamente un limite superiore alla frazione di punti che violano il margine e un limite inferiore alla frazione di support vector. Per esempio $\nu = 0.1$ garantisce che al più il 10% dei campioni violi il margine, e che i support vector siano almeno il 10% dei campioni. L’introduzione del soft margin, in generale, rende la funzione più liscia ma tende ad aumentare il numero di support vector, perché ai punti sul margine si aggiungono tutti quelli che lo violano.

8. Addestrare una SVM in pratica#

8.1 Il costo del problema quadratico#

In linea di principio addestrare una SVM significa solo risolvere il problema duale per trovare gli $\alpha_n$, e poi calcolare $b$. In pratica il problema quadratico (QP) ha costo dell’ordine di $O(N^3)$ nel numero di campioni: con training set grandi l’addestramento diretto è molto costoso. L’inferenza invece è economica, perché usa solo i support vector. Sono state sviluppate tecniche per accelerare l’addestramento, tutte basate sulla stessa strategia: risolvere iterativamente sottoproblemi piccoli invece del problema completo. Esistono anche varianti per l’apprendimento online, quando i dati non sono tutti disponibili all’inizio ma arrivano nel tempo (metodi basati su chunking e metodi incrementali).

8.2 Chunking#

Si costruisce un working set, inizialmente un sottocampione casuale del dataset, e si risolve il problema quadratico solo su di esso, ottenendo dei support vector provvisori. Si applica poi il modello all’intero dataset e si individua il worst set: i punti su cui il modello commette gli errori più gravi. Il nuovo working set è l’unione dei support vector correnti e del worst set, e si itera. La logica: i punti interessanti sono quelli già identificati come support vector più quelli su cui il modello fatica. Il metodo converge alla soluzione ottima, ma ha un difetto: la dimensione del working set non è limitata e può crescere fino a diventare paragonabile al dataset intero, vanificando il vantaggio.

8.3 Metodo di Osuna#

Stessa idea del chunking, ma con working set a dimensione fissa: a ogni iterazione si sostituisce un numero fisso di elementi del working set con altrettanti campioni misclassificati del dataset. La dimensione costante (per esempio il 10% del dataset) garantisce, grazie alla complessità cubica, un guadagno computazionale di ordini di grandezza su ogni sottoproblema. Converge all’ottimo, ma come il chunking richiede molte iterazioni.

8.4 Sequential Minimal Optimization (SMO)#

È l’approccio con le fondamenta teoriche più solide e il più usato in pratica. L’osservazione chiave: se si ottimizza il duale rispetto a due soli moltiplicatori alla volta, tenendo fissi gli altri, il sottoproblema ha soluzione analitica, senza bisogno di alcun solutore numerico (due variabili sono il minimo indispensabile, perché il vincolo $\sum_n \alpha_n t_n = 0$ impedisce di muoverne una sola). SMO itera quindi su coppie di punti, aggiornando ogni volta i loro $\alpha$ in forma chiusa: servono moltissime iterazioni, ma ognuna è praticamente istantanea. Il criterio di arresto tipico è la stabilità della soluzione: ci si ferma quando gli aggiornamenti tra iterazioni successive scendono sotto una soglia.

In parole semplici: invece di risolvere un gigantesco problema di ottimizzazione tutto insieme, SMO lo sbriciola nel più piccolo pezzo possibile, due punti alla volta, per il quale la soluzione si scrive con carta e penna. Tanti micro-passi velocissimi al posto di un macro-passo proibitivo.

9. SVM multi-classe#

La definizione della SVM è intrinsecamente binaria: il margine è la distanza tra due classi. Estendere la formulazione stessa a più classi si è rivelato difficile (molti tentativi, pochi successi), quindi in pratica si decompone il problema multi-classe in più problemi binari, con le strategie generali già viste per i classificatori binari.

• One-against-all: un problema a $k$ classi diventa $k$ problemi binari “classe $i$ contro tutte le altre”. Ogni modello è addestrato sull’intero dataset. In test si applicano tutti i $k$ modelli e si sceglie la classe con il margine più alto, cioè la predizione più confidente. Pochi modelli ma problemi grandi: training costoso, test economico, memoria contenuta; il confronto tra modelli globali rende la scelta della classe piuttosto robusta.

• One-against-one: si addestra un modello per ogni coppia di classi, $k(k-1)/2$ modelli, ciascuno sul sottoinsieme di dati delle due classi coinvolte. In test si applicano tutti i modelli e si sceglie la classe con majority voting. Molti modelli ma problemi piccoli: training complessivamente più leggero per singolo problema, test e memoria costosi. È l’approccio con le prestazioni migliori, grazie alla decomposizione più efficace.
• DAGSVM: addestramento identico a one-against-one, ma il test usa un grafo aciclico diretto di decisione: a ogni nodo un classificatore binario esclude una classe, così per classificare un punto bastano $k-1$ valutazioni invece di $k(k-1)/2$. Accortezza progettuale: i modelli più affidabili vanno posizionati in cima al grafo, perché un errore nei primi nodi esclude la classe giusta senza possibilità di recupero.

In sintesi: one-against-one è il più accurato, DAGSVM ne è un’approssimazione più veloce in test, one-against-all è il più economico in memoria.

10. SVM per regressione (cenni)#

L’idea del margine si può trasportare in regressione rovesciandola. Invece di una zona vuota da massimizzare tra due classi, si definisce un tubo di tolleranza di ampiezza $\epsilon$ attorno alla funzione di regressione: gli errori dei punti che cadono dentro il tubo non vengono penalizzati affatto, mentre si penalizzano solo gli scostamenti oltre $\epsilon$. Rispetto alla regressione classica, che penalizza ogni scostamento per quanto piccolo, si ottiene un metodo più robusto e di nuovo sparso: i support vector sono i punti sul bordo o fuori dal tubo, e solo loro determinano la soluzione. Con i kernel, il tubo può seguire funzioni non lineari arbitrarie. Il corso si limita a questa intuizione, senza sviluppare la formulazione completa.

11. SVM, perceptron e logistic regression a confronto#

Le tre tecniche condividono lo stesso spazio delle ipotesi per la decisione: una funzione lineare (eventualmente in un feature space) di cui si guarda il segno. Ciò che le distingue è come scelgono $\mathbf{w}$ e $b$ dato il dataset:

Il confronto chiarisce il posizionamento delle SVM: rispetto al perceptron aggiungono un criterio di preferenza (il margine) che rende la soluzione unica, riproducibile e più robusta; rispetto alla logistic regression rinunciano all’output probabilistico in cambio di sparsità e di un’integrazione naturale con i kernel.

In parole semplici: perceptron, logistic regression e SVM disegnano tutte una linea di separazione; il perceptron ne trova una qualsiasi, la logistic regression quella più plausibile in senso probabilistico ascoltando tutti i punti, la SVM quella più prudente ascoltando solo i punti di frontiera.

12. Procedura d’esame ed esercizi svolti#

Gli esercizi numerici sulle SVM sono tra i più frequenti in assoluto negli esami del corso. Le due tipologie ricorrenti: analizzare una SVM lineare di cui sono dati $\mathbf{w}$ e $b$ (support vector, margine, classificazione, effetto di nuovi punti) e ricavare da un piccolo dataset 2D la SVM a massimo margine (support vector, $\mathbf{w}$, $b$, margine). Conviene padroneggiare le formule operative e le procedure meccaniche prima di affrontare gli svolgimenti.

12.1 La cassetta degli attrezzi#

Per una SVM lineare $y(\mathbf{x}) = \mathbf{w}^T\mathbf{x} + b$ addestrata (in forma canonica):

1. Confine di decisione: $\mathbf{w}^T\mathbf{x} + b = 0$.
2. Iperpiani di margine: $\mathbf{w}^T\mathbf{x} + b = +1$ (lato positivo) e $\mathbf{w}^T\mathbf{x} + b = -1$ (lato negativo).
3. Margine: $\dfrac{1}{\lVert \mathbf{w} \rVert_2}$; ampiezza totale del corridoio: $\dfrac{2}{\lVert \mathbf{w} \rVert_2}$.
4. Classificazione di un punto: segno di $y(\mathbf{x})$.
5. Test di support vector: si calcola $t_n \, y(\mathbf{x}_n)$. Se vale esattamente $1$: punto sul margine, support vector. Se vale meno di $1$ (incluso negativo): punto dentro il margine o misclassificato, support vector nel caso soft margin. Se vale più di $1$: punto fuori dal margine, non è un support vector.
6. Vincoli sugli $\alpha$: $\mathbf{w} = \sum_n \alpha_n t_n \mathbf{x}_n$, $\sum_n \alpha_n t_n = 0$ (la somma degli $\alpha$ dei positivi uguaglia quella dei negativi), $\alpha_n = 0$ per ogni non support vector.
7. Aggiunta di un punto nuovo: se misclassificato dalla SVM corrente, bisogna sempre riaddestrare; se correttamente classificato e strettamente fuori dal margine ($t \, y(\mathbf{x}) > 1$), la soluzione non cambia e non serve riaddestrare; se correttamente classificato ma sul margine o dentro il margine ($t \, y(\mathbf{x}) \leq 1$), in generale serve riaddestrare perché la soluzione a massimo margine può cambiare (con l’eccezione del punto che cade esattamente sul margine, che può lasciare la soluzione invariata).
8. Rimozione di un punto: se non è un support vector la soluzione resta identica; se è un support vector la soluzione in generale cambia, e il margine può solo aumentare o restare uguale (si è tolto un vincolo, quindi la regione ammissibile si allarga).
9. Numero minimo di support vector: almeno due, almeno uno per classe: su entrambi gli iperpiani di margine deve appoggiarsi almeno un punto, altrimenti si potrebbe allargare il margine.

12.2 Esercizio 1 (da esame): analisi di una SVM lineare data#

Traccia. Si consideri un classificatore SVM lineare definito dai parametri $\mathbf{w} = (2, 1)^T$ e $b = 1$. Rispondere motivando adeguatamente:

1. il punto $\mathbf{x}^{(1)} = (-2, 4)^T$ è un support vector?
2. Fornire un esempio di punto che giace sul confine di decisione.
3. Come viene classificato il punto $\mathbf{x}^{(2)} = (3, -1)^T$?
4. Si raccoglie un nuovo campione $\mathbf{x}^{(3)} = (-1, 2)^T$ di cui si sa che appartiene alla classe negativa. È necessario riaddestrare la SVM?

Svolgimento.

Punto 1. Un punto è un support vector se giace sul margine (o, nel caso soft margin, dentro il margine). Il test è calcolare $y(\mathbf{x}^{(1)})$:

$$y(\mathbf{x}^{(1)}) = \mathbf{w}^T\mathbf{x}^{(1)} + b = 2 \cdot (-2) + 1 \cdot 4 + 1 = -4 + 4 + 1 = 1$$

Il valore è esattamente $+1$: il punto giace sull’iperpiano di margine del lato positivo. Sì, è un support vector, e in particolare sta esattamente sul margine (la risposta completa specifica entrambe le cose).

Punto 2. Il confine di decisione è l’insieme dei punti che soddisfano

$$2 x_1 + x_2 + 1 = 0$$

Basta esibirne uno: scegliendo $x_1 = 0$ si ottiene $x_2 = -1$, quindi il punto $(0, -1)^T$ giace sul confine di decisione. (Qualunque altra soluzione dell’equazione è ugualmente valida.)

Punto 3. Si calcola il valore della funzione discriminante e se ne guarda il segno:

$$y(\mathbf{x}^{(2)}) = 2 \cdot 3 + 1 \cdot (-1) + 1 = 6 - 1 + 1 = 6 > 0$$

Il segno è positivo, quindi il punto è classificato nella classe positiva. Si può aggiungere che $6 > 1$: il punto è ben oltre il margine, la classificazione è molto confidente.

Punto 4. Si calcola $y(\mathbf{x}^{(3)})$ e si confronta con l’etichetta nota $t^{(3)} = -1$:

$$y(\mathbf{x}^{(3)}) = 2 \cdot (-1) + 1 \cdot 2 + 1 = -2 + 2 + 1 = 1 > 0$$

La SVM classifica il punto come positivo, ma la sua classe vera è negativa: il punto è misclassificato, quindi è necessario riaddestrare: la soluzione corrente viola la separazione e il nuovo problema di ottimizzazione produrrà in generale un confine diverso. Vale la pena riportare lo schema decisionale completo, spesso richiesto nella motivazione:

• punto misclassificato: riaddestrare sempre;
• punto correttamente classificato e strettamente fuori dal margine: nessun riaddestramento, la soluzione non cambierebbe (il punto avrebbe $\alpha = 0$);
• punto correttamente classificato ma dentro il margine: riaddestrare, perché il vincolo di quel punto è violato dalla soluzione corrente e il confine a massimo margine cambia;
• caso limite del punto che cade esattamente sul margine: il vincolo è soddisfatto con uguaglianza, la soluzione corrente resta ottima e può non servire riaddestrare (il punto diventa semplicemente un ulteriore support vector).

12.3 Procedura meccanica: trovare la SVM da un dataset 2D#

Data una manciata di punti etichettati nel piano, la procedura per trovare la SVM a massimo margine a mano è la seguente.

1. Disegnare i punti (o ragionare sulle coordinate) e individuare la zona di confine tra le classi: i candidati support vector sono i punti di ciascuna classe più vicini all’altra classe.
2. Sfruttare le simmetrie: se il dataset è simmetrico rispetto a un asse, il confine ottimo rispetta la simmetria (per esempio è verticale o orizzontale) e la forma di $\mathbf{w}$ si semplifica.
3. Caso a due support vector (uno per classe): il confine è l’asse del segmento che li congiunge (perpendicolare al segmento, passante per il punto medio) e il margine è metà della loro distanza. Questo dà anche un limite superiore generale: il margine non può mai superare metà della distanza minima tra punti di classi opposte.
4. Impostare i vincoli canonici sui support vector ipotizzati: $t_n(\mathbf{w}^T\mathbf{x}_n + b) = 1$ per ogni candidato, ed eventualmente la forma di $\mathbf{w}$ suggerita dalla simmetria. Risolvere il sistema lineare per $\mathbf{w}$ e $b$.
5. Verificare tutti gli altri punti: ogni punto non support vector deve soddisfare $t_n(\mathbf{w}^T\mathbf{x}_n + b) \geq 1$. Se un punto viola il vincolo, l’ipotesi sui support vector era sbagliata: quel punto va incluso tra i support vector e si ripete il calcolo. Questa verifica è il passaggio che gli studenti dimenticano più spesso, ed è quella che certifica la soluzione.
6. Calcolare il margine: $1/\lVert \mathbf{w} \rVert_2$.
7. Se richiesti i moltiplicatori: risolvere $\mathbf{w} = \sum_{n \in \mathcal{S}} \alpha_n t_n \mathbf{x}_n$ insieme a $\sum_{n \in \mathcal{S}} \alpha_n t_n = 0$, con $\alpha_n = 0$ fuori da $\mathcal{S}$, e controllare che tutti gli $\alpha_n$ risultino positivi (un $\alpha$ negativo segnala un’ipotesi sbagliata sui support vector).

12.4 Esercizio 2: support vector, pesi e margine da un dataset#

Traccia. È dato il dataset bidimensionale:

Addestrando una SVM lineare hard margin: individuare i support vector, calcolare $\mathbf{w}$, $b$, il margine e i moltiplicatori $\alpha_n$.

Svolgimento.

Passo 1: geometria e candidati. I punti positivi occupano la regione con $x_1 \geq 3$, i negativi la regione con $x_1 \leq 1$. Il dataset è simmetrico rispetto all’asse $x_2 = 0$ (a ogni punto con $x_2 = 1$ corrisponde il gemello con $x_2 = -1$), quindi il confine ottimo è una retta verticale: $\mathbf{w} = (w_1, 0)^T$. I punti positivi più vicini alla zona di confine sono $\mathbf{x}_1 = (3, 1)$ e $\mathbf{x}_2 = (3, -1)$; il negativo più vicino è $\mathbf{x}_5 = (1, 0)$. Candidati support vector: $\mathcal{S} = \{1, 2, 5\}$.

Passo 2: vincoli canonici. Con $\mathbf{w} = (w_1, 0)^T$:

• per $\mathbf{x}_1$ e $\mathbf{x}_2$ (target $+1$): $3 w_1 + b = 1$;
• per $\mathbf{x}_5$ (target $-1$): $-(w_1 + b) = 1$, cioè $w_1 + b = -1$.

Sottraendo la seconda equazione dalla prima: $2 w_1 = 2$, quindi

$$w_1 = 1, \qquad b = -2, \qquad \mathbf{w} = (1, 0)^T$$

Il confine di decisione è $x_1 - 2 = 0$, cioè la retta verticale $x_1 = 2$; gli iperpiani di margine sono $x_1 = 3$ e $x_1 = 1$.

Passo 3: verifica degli altri punti. Si controlla $t_n(\mathbf{w}^T\mathbf{x}_n + b) \geq 1$ per i punti fuori da $\mathcal{S}$:

• $\mathbf{x}_3 = (6, 1)$: $+1 \cdot (6 - 2) = 4 \geq 1$, ok;
• $\mathbf{x}_4 = (6, -1)$: $4 \geq 1$, ok;
• $\mathbf{x}_6 = (0, 1)$: $-1 \cdot (0 - 2) = 2 \geq 1$, ok;
• $\mathbf{x}_7 = (0, -1)$: $2 \geq 1$, ok;
• $\mathbf{x}_8 = (-1, 0)$: $-1 \cdot (-1 - 2) = 3 \geq 1$, ok.

Tutti i vincoli sono soddisfatti: la soluzione è certificata e i support vector sono esattamente $\mathbf{x}_1$, $\mathbf{x}_2$, $\mathbf{x}_5$.

Passo 4: margine.

$$\text{margine} = \frac{1}{\lVert \mathbf{w} \rVert_2} = \frac{1}{\sqrt{1^2 + 0^2}} = 1$$

coerente con la geometria: il confine $x_1 = 2$ dista esattamente 1 sia da $x_1 = 3$ sia da $x_1 = 1$. L’ampiezza totale del corridoio è $2/\lVert \mathbf{w} \rVert_2 = 2$.

Passo 5: moltiplicatori. Si impone $\mathbf{w} = \sum_{n \in \mathcal{S}} \alpha_n t_n \mathbf{x}_n$ e $\sum_{n \in \mathcal{S}} \alpha_n t_n = 0$:

$$\alpha_1 \begin{pmatrix} 3 \\ 1 \end{pmatrix} + \alpha_2 \begin{pmatrix} 3 \\ -1 \end{pmatrix} - \alpha_5 \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \qquad \alpha_1 + \alpha_2 - \alpha_5 = 0$$

Dalla seconda componente della prima equazione: $\alpha_1 - \alpha_2 = 0$, quindi $\alpha_1 = \alpha_2$. Dal vincolo di somma: $\alpha_5 = \alpha_1 + \alpha_2 = 2\alpha_1$. Sostituendo nella prima componente: $3\alpha_1 + 3\alpha_2 - \alpha_5 = 6\alpha_1 - 2\alpha_1 = 4\alpha_1 = 1$, da cui

$$\alpha_1 = \alpha_2 = \frac{1}{4}, \qquad \alpha_5 = \frac{1}{2}, \qquad \alpha_3 = \alpha_4 = \alpha_6 = \alpha_7 = \alpha_8 = 0$$

Tutti gli $\alpha$ dei support vector sono positivi: l’ipotesi era corretta. Verifica incrociata di $b$ con la formula della media sui support vector (kernel lineare $k(\mathbf{x}, \mathbf{x}') = \mathbf{x}^T\mathbf{x}'$):

$$b = \frac{1}{3}\Big[ (1 - 3) + (1 - 3) + (-1 - 1) \Big] = \frac{-6}{3} = -2$$

dove per ciascun $n \in \mathcal{S}$ si è calcolato $t_n - \mathbf{w}^T\mathbf{x}_n$. Il valore coincide con quello trovato prima.

12.5 Esercizio 3: aggiungere e togliere punti#

Traccia. Con riferimento al dataset e alla soluzione dell’esercizio 2 ($\mathbf{w} = (1,0)^T$, $b = -2$, margine 1), dire che cosa succede alla soluzione nei seguenti scenari, ciascuno considerato separatamente:

1. si aggiunge il punto $(5, 0)$ con classe $+1$;
2. si aggiunge il punto $(1.5, 0)$ con classe $+1$;
3. si rimuove il punto $\mathbf{x}_3 = (6, 1)$;
4. si rimuove il support vector $\mathbf{x}_5 = (1, 0)$.

Svolgimento.

Scenario 1: punto nuovo fuori dal margine. Si calcola $t \, y(\mathbf{x}) = +1 \cdot (5 - 2) = 3 > 1$: il punto è correttamente classificato e strettamente oltre il margine. Il suo vincolo è già soddisfatto dalla soluzione corrente, che quindi resta ottima: la soluzione non cambia e il punto avrebbe $\alpha = 0$. Non serve riaddestrare.

Scenario 2: punto nuovo misclassificato. Si calcola $t \, y(\mathbf{x}) = +1 \cdot (1.5 - 2) = -0.5 < 0$: il punto è misclassificato dalla SVM corrente, quindi bisogna riaddestrare. Il dataset resta linearmente separabile (tutti i negativi hanno $x_1 \leq 1$, tutti i positivi, incluso il nuovo, $x_1 \geq 1.5$), quindi la hard margin SVM esiste ancora. I nuovi punti di classi opposte più vicini sono $(1.5, 0)$ e $(1, 0)$, a distanza $0.5$: il margine non può superare $0.25$, e viene realizzato dall’asse del loro segmento, la retta verticale $x_1 = 1.25$. Imponendo i vincoli canonici con $\mathbf{w} = (w_1, 0)^T$: $1.5\, w_1 + b = 1$ e $-(w_1 + b) = 1$, da cui $0.5\, w_1 = 2$, quindi

$$\mathbf{w} = (4, 0)^T, \qquad b = -5, \qquad \text{margine} = \frac{1}{4}$$

Verifica rapida degli altri punti: $\mathbf{x}_1 = (3,1)$: $12 - 5 = 7 \geq 1$; $\mathbf{x}_6 = (0,1)$: $-(0 - 5) = 5 \geq 1$; tutti soddisfatti. Il margine è crollato da $1$ a $0.25$ per colpa di un unico punto: se quel punto fosse rumore, la hard margin SVM ne resterebbe deformata. È esattamente lo scenario in cui conviene una soft margin con $C$ moderato: pagando una slack sul punto anomalo ($\xi = 1 - t\,y(\mathbf{x}) = 1.5$ rispetto al vecchio confine) il modello può mantenere un margine ampio, e per $C$ sufficientemente piccolo la soluzione soft resta vicina a quella originale trattando il punto come outlier.

Scenario 3: rimozione di un non support vector. Il punto $\mathbf{x}_3$ ha $\alpha_3 = 0$ (era stato verificato: $t_3 y(\mathbf{x}_3) = 4 > 1$). La soluzione dipende solo dai support vector, quindi rimuoverlo non cambia assolutamente nulla: stessi $\mathbf{w}$, $b$, margine e support vector.

Scenario 4: rimozione di un support vector. Rimuovendo $\mathbf{x}_5 = (1,0)$ sparisce un vincolo attivo, quindi la soluzione in generale cambia e il margine può solo aumentare o restare uguale. I negativi più vicini diventano $\mathbf{x}_6 = (0, 1)$ e $\mathbf{x}_7 = (0, -1)$; il dataset resta simmetrico rispetto a $x_2 = 0$, quindi si cerca ancora $\mathbf{w} = (w_1, 0)^T$. Vincoli canonici: per $\mathbf{x}_1, \mathbf{x}_2$: $3 w_1 + b = 1$; per $\mathbf{x}_6, \mathbf{x}_7$: $-(0 \cdot w_1 + b) = 1$, cioè $b = -1$. Dalla prima: $3 w_1 = 2$, quindi

$$\mathbf{w} = \left( \tfrac{2}{3}, 0 \right)^T, \qquad b = -1, \qquad \text{margine} = \frac{1}{2/3} = \frac{3}{2}$$

Il confine si sposta in $x_1 = 1.5$ e il margine cresce da $1$ a $1.5$. Verifica di $\mathbf{x}_8 = (-1, 0)$: $-1 \cdot (-\tfrac{2}{3} - 1) = \tfrac{5}{3} \geq 1$, ok; $\mathbf{x}_3, \mathbf{x}_4$: $\tfrac{2}{3} \cdot 6 - 1 = 3 \geq 1$, ok. I nuovi support vector sono $\mathbf{x}_1, \mathbf{x}_2, \mathbf{x}_6, \mathbf{x}_7$.

In parole semplici: la soluzione SVM è insensibile a tutto ciò che accade lontano dal confine: aggiungere o togliere punti tranquilli non la muove di un millimetro. È invece sensibile ai punti di frontiera: aggiungerne uno scomodo restringe il margine (o costringe al soft margin), toglierne uno lo allarga.

12.6 Domande teoriche ricorrenti#

Oltre agli esercizi numerici, alcune domande teoriche ritornano spesso; conviene avere pronta la linea di risposta.

• Derivare il duale dal primale (soft margin): scrivere la lagrangiana con moltiplicatori $\alpha_n$ per i vincoli di margine e $\mu_n$ per $\xi_n \geq 0$; annullare i gradienti rispetto a $\mathbf{w}$, $b$, $\xi_n$ ottenendo $\mathbf{w} = \sum_n \alpha_n t_n \boldsymbol{\phi}(\mathbf{x}_n)$, $\sum_n \alpha_n t_n = 0$ e $\alpha_n = C - \mu_n$; sostituire nella lagrangiana ed eliminare le variabili primali; concludere con l’obiettivo duale e i box constraints $0 \leq \alpha_n \leq C$ (sezione 7.4).
• Perché la soluzione è sparsa: per la condizione KKT di complementarietà $\alpha_n(t_n y(\mathbf{x}_n) - 1) = 0$: i punti fuori dal margine hanno vincolo non attivo e quindi $\alpha_n = 0$ (sezione 5.1).
• Perché massimizzare il margine: robustezza al rumore sui dati di test, unicità e riproducibilità della soluzione (contro l’arbitrarietà del perceptron), e legame con la generalizzazione tramite il bound leave-one-out $L_{LOO} \leq |\mathcal{S}|/N$ (sezioni 2.2, 2.3 e 5.4).
• Ruolo di $C$ e legame col bias-varianza: $C$ grande equivale a poca regolarizzazione (margine rigido, varianza alta), $C$ piccolo a molta regolarizzazione (margine morbido, bias alto); comportamento opposto al $\lambda$ della ridge (sezione 7.3).
• Interpretazione dei valori di $\alpha_n$ nel soft margin: $\alpha_n = 0$ non support vector; $0 < \alpha_n < C$ sul margine; $\alpha_n = C$ dentro il margine o misclassificato a seconda che $\xi_n \leq 1$ o $\xi_n > 1$ (sezione 7.4).

Glossario#

Dispensa Machine Learning · Politecnico di Milano